import java.util.ArrayList;
import java.util.List;

public class LinkedLIst {
    Node head;

    static class Node{

        int data;
        Node next;
        Node(int d){
            data=d;
            next=null;
        }
    }
    public int getCount()
    {
        Node temp = head;
        int count = 0;
        while (temp != null)
        {
            count++;
            temp = temp.next;
        }
        return count;
    }
    public void push(int new_data){
        Node new_node = new Node(new_data);
        new_node.next=head;
        head=new_node;
    }


    public void apppend(int new_data){
        Node new_node = new Node(new_data);
        if(head==null){
            head=new Node(new_data);
            return;
        }
        new_node.next=null;
        Node last = head;
        while (last.next != null){
            last = last.next;
        }
        last.next=new_node;
        return;

    }
    public void printlist(){
        Node n =  head;
        while (n!=null){
            System.out.print(n.data+" ");
            n=n.next;
        }
    }

    public Node deletenode(Node head,int key){
        if (head == null)
            return head;
        head.next = deletenode(head.next, key);
        return head.data == key ? head.next : head;
    }
    public void addArrToNode(int[] arr){
        for(int i= 0;i<arr.length;i++){
            apppend(arr[i]);

        }
    }
    public int GetNth(int index){
        Node current = head;
        int count =0;
        while (current != null){
            if(count==index)
                return current.data;
            count++;
            current = current.next;
        }
        assert (false);
        return 0;
    }
    static Node GetNode(int data) {
        return new Node(data);
    }
    //向指定位置i处添加元素
    public void addNodeByIndex(int index, int data) {
        if (index ==0) {
            push(data);
        }
        int count = 1; //记录遍历的位置
        Node node = new Node(data);
        Node temp = head;
        while (temp.next != null) {
            if (index == count++) {
                node.next = temp.next;
                temp.next = node;
                return;
            }
            temp = temp.next;
        }

    }

    public void move() {
        Node nodeNegative = new Node(0);
        Node curNega = nodeNegative;
        Node cur = head;
        while(cur.next != null) {
            if(cur.next.data < 0) {
                Node add = new Node(cur.next.data);
                add.next = curNega.next;
                curNega.next = add;
                curNega = curNega.next;
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        curNega.next = head;
        head = nodeNegative.next;

    }





    public static void main(String[] args) {
        LinkedLIst llist = new LinkedLIst();
        LinkedLIst lllist = new LinkedLIst();
        LinkedLIst llllist = new LinkedLIst();
        int[] arr = {1,2,3,4,5};
        lllist.addArrToNode(arr);
        lllist.push(5);
        lllist.push(4);
        lllist.push(3);
        lllist.push(2);
        lllist.push(1);


        llist.apppend(1);
        llist.apppend(2);
        llist.apppend(2);
        llist.apppend(3);
        llist.apppend(1);
        llist.deletenode(llist.head,2);
        llist.printlist();

        llllist.apppend(1);
        llllist.apppend(2);
        llllist.apppend(-1);
        llllist.apppend(-2);
        llllist.apppend(-3);
        llllist.apppend(-3);
        llllist.apppend(4);
        llllist.move();
        llllist.printlist();




        lllist.addNodeByIndex(0,6);
        lllist.printlist();





    }
}
